package com.dyz.leetcode._12_linkedList;

import com.dyz.leetcode.ListNode;

public class _86_partition {
    public ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null){return head;}
        ListNode smallHead = new ListNode(-1);
        ListNode small = smallHead;
        ListNode largeHead = new ListNode(-1);
        ListNode large = largeHead;

        while (head!=null){
            if(head.val<x){
                small.next = new ListNode(head.val);
                small = small.next;
            }else {
                large.next = new ListNode(head.val);
                large = large.next;
            }
            head = head.next;
        }
        small.next = largeHead.next;

        return smallHead.next;
    }
}
